import java.awt.*;

/**
 * 三路快速排序
 */
public class AlgoVisualizer4 {

    private ThreeWaysQuickSortData data;
    private AlgoFrame4 frame;
    private static int DELAY = 20;

    public AlgoVisualizer4(int sceneWidth, int sceneHeight, int N, ThreeWaysQuickSortData.Type dataType) {
        // 初始化数据
        data = new ThreeWaysQuickSortData(N, sceneHeight, dataType);

        EventQueue.invokeLater(() -> {
            frame = new AlgoFrame4("Quick Sort Visualization", sceneWidth, sceneHeight);

            // https://docs.oracle.com/javase/tutorial/uiswing/concurrency/dispatch.html
            // Tasks on the event dispatch thread must finish quickly; if they don't, unhandled events back up and the user interface becomes unresponsive.
            new Thread(this::run).start();
        });
    }

    public AlgoVisualizer4(int sceneWidth, int sceneHeight, int N) {
        this(sceneWidth, sceneHeight, N, ThreeWaysQuickSortData.Type.Default);
    }

    // 动画逻辑
    private void run() {
        setData(-1, -1, -1, -1, -1, -1);
        quickSort3Ways(0, data.N() - 1);
        setData(-1, -1, -1, -1, -1, -1);
    }

    private void quickSort3Ways(int l, int r) {
        if (l > r) {
            return;
        } else if (l == r) {
            setData(l, r,  l, -1, -1, -1);
            return;
        }

        // 使用随机位置的元素作为标定点
        int p = (int) (Math.random() * (r - l + 1)) + l;
        setData(l, r, -1, p, -1, -1);

        data.swap(l, p);
        int v = data.get(l);
        setData(l, r, -1, l, -1, -1);

        // 三路快排的 partition
        // arr[l+1...lt] < v
        int lt = l;
        // arr[gt...r] > v
        int gt = r + 1;
        // arr[lt+1...i] = v
        int i = l + 1;
        setData(l, r, -1, l, lt, gt);

        while (i < gt) {
            if (data.get(i) < v) {
                data.swap(i, lt + 1);
                i ++;
                lt ++;
            } else if (data.get(i) > v) {
                data.swap(i, gt - 1);
                gt --;
            } else {
                i ++;
            }
            setData(l, r, -1, l, i, gt);
        }

        data.swap(l, lt);
        setData(l, r, lt, -1, -1, -1);

        quickSort3Ways(l, lt - 1);
        quickSort3Ways(gt, r);
    }


    private void setData(int l, int r, int fixedPivot, int curPivot, int curL, int curR) {
        data.l = l;
        data.r = r;
        if (fixedPivot != -1) {
            int i = fixedPivot;
            while (i < data.N() && data.get(i) == data.get(fixedPivot)) {
                data.fixedPivots[i] = true;
                i ++;
            }
        }
        data.curPivot = curPivot;
        data.curL = curL;
        data.curR = curR;

        frame.render(data);
        AlgoVisHelper.pause(DELAY);
    }

    public static void main(String[] args) {
        int sceneWidth = 800;
        int sceneHeight = 800;
        int N = 100;

//        AlgoVisualizer4 visualizer1 = new AlgoVisualizer4(sceneWidth, sceneHeight, N);

        // 当数据是近乎有序的时候，算法变成了 O(n^2) 级别的算法。
//        AlgoVisualizer4 visualizer = new AlgoVisualizer4(sceneWidth, sceneHeight, N, ThreeWaysQuickSortData.Type.NearlyOrdered);

        // 当数据一样的时候，算法变成了 O(n^2) 级别的算法。
        AlgoVisualizer4 visualizer = new AlgoVisualizer4(sceneWidth, sceneHeight, N, ThreeWaysQuickSortData.Type.Identical);
    }
}
